package com.rui.shangXueTang.select;

/**
 * @author : [锐神NO.3]
 * @version : [v1.0]
 * @className : InsertSearch
 * @createTime : [2022/2/16 14:58]
 * @description : [插值查找]
 */

public class InsertSearch {
    public static void main(String[] args) {

        int[] arr = {1,2,3,4,5,6,7,8,9,10};

        int index = insertSearch(arr, 8);

        System.out.println(index);
    }

    private static int insertSearch(int[] arr, int target){
        int left = 0;
        int right = arr.length - 1;

        while(left <= right){
            int mid = left + (right - left) * (target - arr[left]) / (arr[right] - arr[left]);
            if(target > arr[mid]){
                left = mid + 1;
            }else if(target < arr[mid]){
                right = mid - 1;
            }else {
                return mid;
            }
        }
        return -1;
    }
}
